class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}



public class Solution725 {

    private int getLen(ListNode tmpNode){
        int len = 0;
        while(tmpNode != null){
            len++;
            tmpNode = tmpNode.next;
        }
        return len;
    }

    private int[] getSplitPlan(int len, int k){
        int[] res = new int[k];
        int ind = 0;
        int tmpLen;
        while(len % k != 0){
            tmpLen = len / k + 1;
            len -= tmpLen;
            k--;
            res[ind] = tmpLen;
            ind++;
        }
        tmpLen = len / k;
        while(ind < res.length){
            res[ind] = tmpLen;
            ind++;
        }
        return res;
    }

    public ListNode[] splitListToParts(ListNode head, int k) {
        int len = getLen(head);
        int[] splitPlan = getSplitPlan(len, k);
        ListNode tmpNode = head;
        ListNode[] res =new ListNode[k];
        int ind = 0;
        for (int i = 0; i < splitPlan.length; i++) {
            res[ind] = tmpNode;
            int tmpLen = splitPlan[i];
            for (int j = 1; j <= tmpLen; j++) {
                ListNode nextNode = tmpNode.next;
                if(j == tmpLen){
                    tmpNode.next = null;
                }
                tmpNode = nextNode;
            }
            ind++;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution725 s = new Solution725();
        int[] res = s.getSplitPlan(3, 5);
        System.out.println(res);
    }
}
